package com.wang.sort3;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @Author: along
 * @Create: 2021/4/22
 * @Description:做项目的问题
 */
public class Demo05_IPO {
    //初始化
    public static class Program{
        public int p;
        public int c;

        public Program(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }
    //重写比较器
    public static class MinCostComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o1.c - o2.c;
        }
    }
    public static class MaxProfitComparator implements Comparator<Program> {

        @Override
        public int compare(Program o1, Program o2) {
            return o2.p - o1.p;
        }
    }
    //k为可做的项目个数，w为初始资金，profits为项目利润 capital为项目投资
    public static  int findMaximizedCapital(int k, int w, int[] Profits, int[] Capital) {
        PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());//按照花费建立的小根堆
        PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());//按照利润建立的大根堆

        for (int i = 0; i < Profits.length; i++) {
            minCostQ.add(new Program(Profits[i], Capital[i]));
        }
        //循环k - 1轮次 因为有k个项目要加到小根堆种
        for (int i = 0; i < k ; i++) {
            //只要小根堆不为空，把项目弹出加到大根堆中
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= w) {
                maxProfitQ.add(minCostQ.poll());
            }
            //大根堆为空 无项目可做/项目投入大于启动资金 提前返回
            if(maxProfitQ.isEmpty()) {
                return w;
            }
            w += maxProfitQ.poll().p;
        }
        return w;
    }
}
